#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "heap.h"



/**
 * @brief 创建二叉堆，堆的容量以参数传入，如果参数非法（size <= 0），则创建默认大小的堆
 * 
 * @return
 */
heap_t* create_heap(int size)
{
    heap_t* heap;
    int cap;
    
    if ( (heap = malloc(sizeof(heap_t))) == NULL) {
        printf("in create_heap()_1, malloc faild\n");
        return NULL;
    }
    memset(heap, 0, sizeof(heap_t));

    // 如果size非法，则申请默认大小的内存
    cap = size <= 0 ? DEFAULT_HEAP_SIZE : size;
    heap->capacity = cap;

    // 申请空间失败，则释放之前申请的内存
    if ( (heap->arr = malloc(sizeof(int) * cap)) == NULL) {
        printf("in create_heap()_2, malloc faild\n");
        free(heap);
        return NULL;
    }
    memset(heap->arr, 0, sizeof(int) * cap);

    return heap;
}


/**
 * @brief 二叉堆的容量
 * 
 * @param heap 
 * @return int 
 */
int capacity(heap_t* heap)
{
    if (heap == NULL) {
        printf("in capacity(), heap == NULL(arg error)\n");
        return -1;
    }
    return heap->capacity;
}


/**
 * @brief 销毁目标二叉堆
 * 
 * @param 要销毁的二叉堆 
 */
int destroy_heap(heap_t* heap)
{
    if (heap == NULL) {
        printf("in destroy_heap(), heap == NULL(arg error)\n");
        return -1;
    }
    
    if (heap->arr != NULL) {
        free(heap->arr);
    }
    free(heap);
    return 0;
}


/**
 * @brief 返回二叉堆的有效元素数量
 * 
 * @param heap 
 * @return int 
 */
int size(heap_t* heap)
{
    if (heap == NULL) {
        printf("in size(), heap == NULL(arg error)\n");
        return -1;
    }
    return heap->size;
}


/**
 * @brief 判断二叉堆是否为空，即堆中没有一个有效元素
 * 
 * @param heap 
 * @return int 
 */
int is_empty(heap_t* heap)
{
    if (heap == NULL) {
        printf("in is_empty(), heap == NULL(arg error)\n");
        return -1;
    }
    return heap->size == 0;
}


/**
 * @brief 清空二叉堆，即将所有数据清零
 * 
 * @param heap 
 */
int clear(heap_t* heap)
{
    if (heap == NULL) {
        printf("in clear(), heap == NULL(arg error)\n");
        return -1;
    }

    if (heap->arr != NULL) {
        memset(heap->arr, 0, sizeof(int) * heap->capacity);
    }
    return 0;
}


/**
 * @brief 添加元素后，新元素值大于父节点，进行上滤
 * 
 * @param index 
 */
void sift_up(heap_t* heap, int index)
{
    int parent_index;
    int tmp, parent;

    tmp = heap->arr[index];
    while (index > 0) {
        parent_index = (index - 1) / 2;
        parent = heap->arr[parent_index];

        if (parent >= tmp) {
            break;
        }

        heap->arr[index] = parent;
        index = parent_index;
    }
    heap->arr[index] = tmp;
}

/**
 * @brief 给二叉堆中添加新的元素
 * 
 * @param heap 
 */
int add(heap_t* heap, int val)
{
    if (heap == NULL || heap->arr == NULL) {
        printf("in add(), heap == NULL || heap->arr == NULL(arg error)\n");
        return -1;
    }

    // 如果堆满了，则要扩容，堆容量变为原来的1.5倍
    if (heap->size >= heap->capacity) {
        int newcap = heap->capacity * 1.5;
        int* newarr;
        if ( (newarr = malloc(sizeof(int) * newcap)) == NULL){
            printf("in add(), malloc faild\n");
            return -1;
        }
        memset(newarr, 0, sizeof(int) * newcap);

        // 迁移旧数据，数据量是扩容之前堆的容量
        memmove(newarr, heap->arr, sizeof(int) * heap->capacity);

        // 更新堆容量
        heap->capacity = newcap;

        // 释放旧的堆空间
        free(heap->arr);
        heap->arr = newarr;
    }

    // 添加新元素
    heap->arr[heap->size] = val;

    // 添加完元素，可能需要上滤调整
    sift_up(heap, heap->size);

    // 有效元素数量加1
    heap->size++;

    return 0;
}


/**
 * @brief 取堆顶元素
 * 
 * @param heap 
 * @return int
 */
int get_top(heap_t* heap)
{
    if (heap == NULL || heap->arr == NULL) {
        printf("in get_top(), heap == NULL || heap->arr == NULL || heap->size == 0(arg error)\n");
        return -1;
    }

    if (heap->size == 0) {
        printf("heap empty\n");
        return -1;
    }

    return heap->arr[0];
}


/**
 * @brief 删除元素后，进行下滤
 * 
 * @param heap 
 * @param
 */
void sift_down(heap_t* heap, int index)
{
    int child_index, right_index, half_index;
    int top_val, child_val;

    top_val = heap->arr[index];
    half_index = heap->size / 2;

    while (index < half_index) {
        // 左子节点的索引
        child_index = index * 2 + 1;
        child_val = heap->arr[child_index];

        // 右子节点的索引(可能没有右子节点)
        right_index = child_index + 1;
        

        // 有右孩子，则选左右较大者
        if (right_index < heap->size && heap->arr[right_index] > child_val) {
            child_index = right_index;
            child_val = heap->arr[right_index];
        }

        if (top_val >= child_val) {
            break;
        }

        heap->arr[index] = child_val;
        index = child_index;
    }
    heap->arr[index] = top_val;
}

/**
 * @brief 删除堆顶元素
 * 
 * @param heap 
 * @return int 
 */
int remove_top(heap_t* heap)
{
    int end_index;

    if (heap == NULL || heap->arr == NULL || heap->size == 0) {
        printf("in remove_top(), heap == NULL || heap->arr == NULL || heap->size == 0(arg error)\n");
        return -1;
    }

    // 删除堆顶元素，如果只有一个有效元素，删完直接退出
    end_index = --heap->size;
    if (heap->size <= 0) {
        return 0;
    }
    
    // 把最后一个元素移到堆顶
    heap->arr[0] = heap->arr[end_index];

    // 调整堆
    sift_down(heap, 0);

    return 0;
}


/**
 * @brief 替换堆顶元素，并返回之前的堆顶元素
 * 
 * @param heap 
 * @return int 
 */
int replace_top(heap_t* heap, int val)
{
    int tmp;

    if (heap == NULL || heap->arr == NULL) {
        printf("in replace_top(), heap == NULL || heap->arr == NULL(arg error)\n");
        return -1;
    }

    // 如果有0个元素
    if (heap->size == 0) {
        heap->arr[0] = val;
        heap->size++;
        printf("in replace_top(), size == 0\n");
        return val;
    }

    // 先保存堆顶元素
    tmp = heap->arr[0];

    // 直接覆盖堆顶元素
    heap->arr[0] = val;

    // 下滤
    sift_down(heap, 0);

    return tmp;
}


/****************************** END OF FILE ******************************/
